#include <vector>
using namespace std;
class Solution
{
public:
    // 思路：  从矩阵的右上角开始搜索，如果当前元素等于目标值，则返回 true；
    // 如果当前元素大于目标值，则向左移动一列；
    // 如果当前元素小于目标值，则向下移动一行。重复此过程直到找到目标值或超出矩阵边界。
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int rows = matrix.size();         // 行数
        int right = matrix[0].size() - 1; // 最后一列的索引
        int top = 0;                      // 第一行的索引
        while (top < rows && right >= 0)  // 在矩阵边界内
        {
            if (matrix[top][right] == target) // 找到了
            {
                return true;
            }
            else if (matrix[top][right] > target) // 当前元素大于目标值，向左移动一列
            {
                --right;
            }
            else // 当前元素小于目标值，向下移动一行
            {
                ++top;
            }
        }
        return false; // 没有找到
    }
};